package day08;

/**
 * 递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
 *
 * 示例1:
 *
 *  输入：A = 1, B = 10
 *  输出：10
 * 示例2:
 *
 *  输入：A = 3, B = 4
 *  输出：12
 */
public class Solution4 {
    public int multiply(int A, int B) {
        if(A==0||B==0){
            return 0;
        }
        int num = multiplication(A,B);
        if((A<0&&B<0)||(A>0&&B<0)){
            return -num;
        }
        return num;
    }
    public int multiplication(int A,int B){
        if(B==1||B==-1){
            return A;
        }
        return B%2==0?multiplication(A<<1,B>>1):multiplication(A<<1,B>0?B-1>>1:B+1>>1)+A;
    }
}
